[NOI2012]-迷失游乐园

树形dp, 概率与期望

传送门

看起来巨复杂的一道期望嗷，但是基环树还是比较套路的

先考虑纯树的情况：设 $f[x]$ 为 $x$ 往下走的期望，$g[x]$ 为往上走的期望

$f[x] = \frac{1}{son[x]} \sum (f[y] + w(x, y))$，$g[y] = w(x, y) + \frac{g[x] + f[x] \times son[x] - (f[y] + w(x, y))}{son[x] - [x == root]}$ 注意分母可能为 0，要特判。
$ans[x] = \frac{f[x] \times son[x] + g[x]}{son[x] + [x \neq root]}$

好啦 50 分到手，再来想想基环树，发现环上节点好少啊，不管怎样先用同样的思路撕烤撕烤

发现 $f$ 和不在环上的点的 $g$ 和 $ans$ 是一样计算的，环上点的 $g$ 搞出来以后可以把不在环上点的 $g$ 也算出来

对于环上点，对于两个方向都做一遍，以向左为例，$l[x] = \frac{l[nxt] + f[nxt]}{2}$, $g[x] = \frac{l[x] + r[x]}{2}$, $ans[x] = \frac{f[x] \times son[x] + g[x] \times 2}{son[x] + 2}$

就做完了

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 1e5 + 10;
int n, m, top, idx;
int stk[N], dfn[N], son[N];
int to[N << 1], nxt[N << 1], lnk[N], cnt, w[N << 1];
double f[N], g[N], ans;
bool onc[N];

void add(int x, int y, int z) {
    to[++cnt] = y, nxt[cnt] = lnk[x], lnk[x] = cnt, w[cnt] = z;
}

void getf(int x, int fa) {
    f[x] = 0;
    son[x] = 0;
    for (int i = lnk[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y == fa || onc[y]) continue;
        ++son[x];
        getf(y, x);
        f[x] += f[y] + w[i];
    }
    if (son[x]) f[x] /= son[x];
}

void getg(int x, int fa, int op) {
    for (int i = lnk[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y == fa || onc[y]) continue;
        if (op == 1) {
            if (x == 1) {
                if (son[x] == 1) {
                    g[y] = w[i];
                } else {
                    g[y] = w[i] + (f[x] * son[x] - (f[y] + w[i])) / (son[x] - 1);
                }
            } else {
                g[y] = w[i] + (g[x] + f[x] * son[x] - (f[y] + w[i])) / son[x];
            }
        } else {
            if (onc[x]) {
                g[y] = w[i] + (g[x] * 2 + f[x] * son[x] - (f[y] + w[i])) / (son[x] + 1);
            } else {
                g[y] = w[i] + (g[x] + f[x] * son[x] - (f[y] + w[i])) / son[x];
            }
        }
        getg(y, x, op);
    }
}

void solve1() {
    getf(1, 0);
    getg(1, 0, 1);
    ans = f[1];
    rep(i, 2, n)
        ans += (f[i] * son[i] + g[i]) / (son[i] + 1);
    printf("%.5lf\n", ans / n);
}

bool findcir(int x, int fa) {
    stk[++top] = x;
    dfn[x] = ++idx;
    for (int i = lnk[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y == fa) continue;
        if (!dfn[y]) {
            if (findcir(y, x)) return 1;
        } else if (dfn[y] < dfn[x]) {
            while (top && stk[top] != y) onc[stk[top--]] = 1;
            onc[y] = 1;
            return 1;
        }
    }
    --top;
    return 0;
}

double calc(int x, int fa, int st) {
    for (int i = lnk[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y == fa || !onc[y]) continue;
        if (y == st) return f[x];
        else return (calc(y, x, st) + w[i] + f[x] * son[x]) / (son[x] + 1);
    }
    return 0;
}

void calcg(int x) {
    for (int i = lnk[x]; i; i = nxt[i]) {
        int y = to[i];
        if (!onc[y]) continue;
        g[x] += calc(y, x, x) + w[i];
    }
    g[x] /= 2;
}

void solve2() {
    findcir(1, 0);
    rep(i, 1, n)
        if (onc[i]) getf(i, 0);
    rep(i, 1, n)
        if (onc[i]) calcg(i);
    rep(i, 1, n)
        if (onc[i]) getg(i, 0, 2);
    rep(i, 1, n)
        if (!onc[i]) ans += (f[i] * son[i] + g[i]) / (son[i] + 1);
        else ans += (f[i] * son[i] + g[i] * 2) / (son[i] + 2);
    printf("%.5lf\n", ans / n);
}

int main() {
    cin >> n >> m;
    rep(i, 1, m) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        add(x, y, z), add(y, x, z);
    }
    if (n > m) solve1();
    else solve2();
    return 0;
}